#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double db;

#define in read()
#define pii pair<int,int>
#define fi first
#define se second
#define FILE(x) freopen(x".in","r",stdin);\
	freopen(x".out","w",stdout);
#define pb push_back

int read(){
	int x = 0,sgn = 1;char ch = getchar();
	for(;!isdigit(ch);ch = getchar()) if(ch == '-') sgn = -1;
	for(;isdigit(ch);ch = getchar()) x = (x<<1)+(x<<3)+(ch^48);
	return x*sgn;
}

const int N = 1e6+10;

ll s[N],f[N];
int n,m,x[N],h,t,q[N],g[N];

ll sq(ll x){return x * x;}

ll Y(int x){return f[x] + s[x] * s[x];}

db slope(int x,int y){return ((db)Y(x) - Y(y)) / (s[x] - s[y]);}

void dp(ll cost){
	h = 1;t = 0;
	for(int i = 1;i <= n;i++){
		while(h < t && slope(q[t-1],q[t]) > slope(q[t],i-1)) t--;
		q[++t] = i - 1;
		while(h < t && slope(q[h],q[h+1]) < 2 * (s[i] + 1)) h++;
		f[i] = f[q[h]] + sq(s[i] - s[q[h]] + 1) + cost;
		g[i] = g[q[h]] + 1;
	}
}

int main (){
#ifndef ONLINE_JUDGE
	freopen("1.in","r",stdin);
#endif
	n = in,m = in; for(int i = 1;i <= n;i++) x[i] = in;
	for(int i = 1;i <= n;i++) s[i] = s[i-1] + x[i];
	ll l = 0,r = 0x3f3f3f3f3f3f3f3f;
	while(l <= r){
		ll mid = l + r >> 1;
		dp(mid);
		if(g[n] <= m) r = mid - 1;
		else l = mid + 1;
	}
	dp(l); printf("%lld\n",f[n] - 1ll * l * m);
	return 0;
}
